Automatic tracking systems are of increasing interest for applications in which one wishes to identify large number of objects, and follow their trajectories over time. Two examples of such applications would be battlefield tracking of missiles and aircraft, and air traffic control. In both applications, a tracking system, such as a radar coupled with other detection and processing equipment, follows a plurality of objects by scanning over a finite time period, and performs tracking by matching the echoes the objects produce from one scan with those from earlier scans.
The simplest way to perform this matching is to record each report received during each scan from each object in the form of a data vector whose components are the information the system can glean from the object, and which the system can record as simple numerical magnitudes. Examples of such data are range, bearing, radar brightness, doppler shift, infrared signature, etc. Report vectors from one scan are sequentially compared with those of the other, the components of the reports being combined according to a preselected mathematical criterion to calculate a measure of "likeness." Pairs of reports from sequential scans which are most "like" one another according to this criterion are identified as belonging to the same object, this pairing being generally called "gating." In this manner, objects are tracked from scan to scan. Because scanning occurs over a known time, and tracking from one scan to another indicates the distance traveled during that time, one can infer kinematic information (velocity and acceleration) using reports from several scans. When a report data set is augmented by kinematic information, the resulting data are referred to as a "track data set," or simply as "tracks."
The sequential comparison of reports in this manner is typically done according to known principles by arranging the report data set from one scan in a search tree, and processing each report from the next scan in the tree.
Although simple in principle, the computation necessary to correlate reports in this manner becomes prohibitively large very quickly. The computational cost necessary to do this correlation is proportional to N.sup.2, where N is the number of tracked objects. As the number of objects becomes large, such as on a busy and crowded battlefield or near a congested urban airport, the computational steps necessary to track the objects becomes so large that only a supercomputer could do the calculations quickly enough to be of practical use. The response to this problem was to seek ways to reduce the number of correlations necessary by identifying a priori, and in a computationally efficient way, pairs of reports from sequential scans which have virtually no probability of correlating, and discarding them prior to forming the search tree. Stated another way, one identifies data vectors from sequential scans which are so distant from one another in the parameter space defined by the components of the report data vectors, that there is virtually no likelihood that they are reports from the same object. One determines what is or is not "distant" using analytic geometry and vector analysis to mathematically surround each report by a preselected volume in parameter space. Points within the volume ar deemed "near" the report, those outside are deemed "distant." Hence, reports from two sequential scans whose volumes do not overlap are distant from one another, and may be discarded before forming a search tree.
However, this approach does not eliminate all inefficiencies. The longer the scan period, the greater the uncertainty in each component of the data vectors. Thus as scan time increases, the volumes in parameter space with which one surrounds the reports one must increase nonlinearly to ensure reliable results, the increase being proportional to the order of the vectors. Thus if scan time doubles, and the data vectors have five components, then search time per object increases proportional to 2.sup.5, i.e. thirty-two fold. In response, one can use kinematic information to "copy" reports from one scan to another, i.e. use kinematics associated with reports from one scan to project those reports to a point in time within the next scan. The reports received in the later scan, and the tracks, are thus moved much closer in time to one another, reducing markedly the volumes in parameter space one must search.
U.S. patent application Ser. No. 07/693,469, by Zuniga et al. discloses a system which further improves computational efficiency by partitioning the scan time into subintervals, copying track data sets sequentially to each subinterval, and updating the track data set at each subinterval. The uncertainty in the tracks and reports are thus much smaller because the time intervals between copies of the tracks is much smaller. Although repeatedly copying the tracks requires additional computations, as the number of objects to be tracked increases, and the order of the data vectors used to track them increases, the savings resulting from increasingly smaller search volumes quickly outweighs the increased cost of repeatedly copying the tracks and repeatedly setting up search trees at each subinterval. Zuniga et al. further discloses how to calculate the tradeoff between these costs, so as to determine the computationally optimal number of subintervals.
As seen from the foregoing, the progression in this art has been from a brute force correlation of reports from scan to scan, to increasingly sophisticated ways of coping track data structures forward to the vicinity in time of new reports, so as to reduce the volumes in parameter space one must search to correlate tracks and reports. A constant, however, has been that tracks are copied, and correlation proceeds by using the tracks to construct a search tree, against which one compares the reports. The reason is that, reports having little or no kinematic information, there is no way to copy reports so as to cluster reports at one time in order to set up a search tree against which to compare tracks. Thus it had been thought that one cannot use reports to construct search trees.